package com.chj.dfs.class04;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

//https://www.jianshu.com/p/d54f0b1db64a

public class Code18_WordLadderII {
	public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
		// 答案
		List<List<String>> ans = new ArrayList<>();
		// word 转化为 ID的哈希表
		HashMap<String, Integer> wordToId = new HashMap<>();
		// id转化为word的数组
		List<String> IdToWord = new ArrayList<>();

		int id = 0;
		for (String word : wordList) {
			wordToId.put(word, id++);
			IdToWord.add(word);
		}
		// wordList如果没有找到endWord
		if (!wordToId.containsKey(endWord)) {
			return ans;
		}
		// 加入beginWord
		if (!wordToId.containsKey(beginWord)) {
			wordToId.put(beginWord, id++);
			IdToWord.add(beginWord);
		}
		// 创建邻接表
		ArrayList<Integer>[] edges = new ArrayList[IdToWord.size()];
		for (int i = 0; i < IdToWord.size(); i++) {
			edges[i] = new ArrayList<>();
		}
		// 添加边
		for (int i = 0; i < IdToWord.size(); i++) {
			for (int j = i + 1; j < IdToWord.size(); j++) {
				// 当距离为1，添加两个点为邻边
				if (distance(IdToWord.get(i), IdToWord.get(j)) == 1) {
					edges[i].add(j);
					edges[j].add(i);
				}
			}
		}
		// 这个cost记录beginword到所有点的最短距离
		int[] cost = new int[IdToWord.size()];
		// 先一开始初始化为最大值
		for (int i = 0; i < cost.length; i++) {
			cost[i] = Integer.MAX_VALUE;
		}
		// 起点为0
		cost[wordToId.get(beginWord)] = 0;

		// 找到目标点
		int destId = wordToId.get(endWord);
		// 这个队列中保存的路径
		Queue<ArrayList<Integer>> queue = new LinkedList<>();
		// 先将起点加入
		ArrayList<Integer> begin = new ArrayList<>();
		begin.add(wordToId.get(beginWord));
		queue.add(begin);

		// 开始BFS
		while (!queue.isEmpty()) {
			// 取出一条路径
			ArrayList<Integer> current = queue.poll();
			// 取出最后一个路径下的最后节点
			int last = current.get(current.size() - 1);
			// 判断路径的最后节点是否是endWord
			if (IdToWord.get(last).equals(endWord)) {
				// 保存下来，把ID值转化为String
				ArrayList<String> tmp = new ArrayList<>();
				for (int i = 0; i < current.size(); i++) {
					tmp.add(IdToWord.get(current.get(i)));
				}
				ans.add(tmp);
			} else {
				// 记录下最后节点有多少相邻边
				int size = edges[last].size();
				// 开始遍历
				for (int i = 0; i < size; i++) {
					// 取出相邻节点
					int to = edges[last].get(i);
					// 判断，这里不需要判断是否访问过，因为如果访问过，那下面这个不等式一定不会成立。且需要用等号，因为不能排除相等长度的路径
					if (cost[last] + 1 <= cost[to]) {
						// 更新距离
						cost[to] = cost[last] + 1;
						// 保存新的路径，先将之前的路径保存下来
						ArrayList<Integer> tmp = new ArrayList<>(current);
						// 添加新的节点to，入队列
						tmp.add(to);
						queue.add(tmp);
					}
				}
			}
		}
		return ans;

	}

	static int distance(String a, String b) {
		int cnt = 0;
		for (int i = 0; i < a.length(); i++) {
			if (a.charAt(i) != b.charAt(i)) {
				cnt++;
			}
		}
		return cnt;
	}

	public static void main(String[] args) {
		String beginWord = "hit";
		String endWord = "cog";
		List<String> wordList = new ArrayList<String>();
//		{"hot","dot","dog","lot","log","cog"};
		wordList.add("hot");
		wordList.add("dot");
		wordList.add("dog");
		wordList.add("lot");
		wordList.add("log");
		wordList.add("cog");

		List<List<String>> count = findLadders(beginWord, endWord, wordList);
		System.out.println(count);
	}
}

//输入:
//beginWord = "hit",
//endWord = "cog",
//wordList = ["hot","dot","dog","lot","log","cog"]
//
//输出:
//[
//["hit","hot","dot","dog","cog"],
//["hit","hot","lot","log","cog"]
//]
